package link.singlyLinkedList;

import java.util.function.Consumer;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/10
 *
 * 单项链表
 */
public class SinglyLinkedList {

    // 头指针，初始为空
    private Node head = null;

    private static class Node{
        // 节点值
        int value;

        // 下一个节点指针
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 给链表头部添加节点
     * @param value 节点值
     */
    public void addFirst(int value) {

//        // 如果头节点为空，则给头节点赋值
//        if (head == null) {
//            head = new Node(value, null);
//        }else {
//            //如果头节点不为空，则使其成为头节点，并使next指向之前的节点(head)
//            head= new Node(value, head);
//        }

        // 化简之后的代码
        head= new Node(value, head);

    }

    /**
     * 遍历链表-while
     */
    public void loop1(Consumer<Integer> action) {
        // 指针从头节点开始
        Node  p = head;

        // 当p不为空时，打印节点值
        while (p != null) {
            action.accept(p.value);
            // 并指向下一个节点
            p = p.next;
        }
    }

    /**
     * 遍历链表-for
     */
    public void loop2(Consumer<Integer> action) {
        for (Node p = head; p != null; p = p.next) {
            action.accept(p.value);
        }
    }

    /**
     * 获取最后一个节点
     * @return 最后一个节点
     */
    private Node findLast() {
        if (head == null) {
            return null;
        }

        Node p = head;

        while (p.next != null) {
            p = p.next;
        }

        return p;
    }

    /**
     * 给链表尾部添加节点
     * @param value 节点值
     */
    public void addLast(int value) {
        // 查找最后一个节点
        Node last = findLast();

        if (last == null) {
            // 链表为空
            head = new Node(value, head);
            return;
        }

        // 使最后一个节点的next指向待插入的节点，待插入节点的下一个节点指向null
        last.next = new Node(value, null);

    }

    /**
     * 根据索引找节点
     * @param index 索引
     * @return 节点
     */
    private Node findNode(int index) {
        int i = 0;
        for (Node p = head; p != null; p = p.next, i++) {
            if (i == index) {
                // 找到则返回
                return p;
            }
        }
        // 找不到返回null
        return null;
    }

    /**
     * 根据索引查找节点值
     * @param index 索引
     * @return 节点值
     */
    public int getValue(int index) {
        // 先查找节点
        Node node = findNode(index);
        if (node == null) {
            // 找不到返回-1
            return -1;
        }
        // 找到返回实际值
        return node.value;
    }

    /**
     * 插入指定位置的节点
     * @param index 待插入索引
     * @param value 待插入节点值
     */
    public void add(int index, int value) {

        // 当索引为0时，相当于给头部插入
        if (index == 0) {
            head = new Node(value, head);
            return;
        }

        // 查找上一个待插入位置的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            // 如果上一个节点不存在，则直接报错
            throw new RuntimeException("索引异常");
        }

        // 将上一个节点的next指向插入的节点，并且新节点的next指向上一个节点之前的next
        prev.next = new Node(value, prev.next);
    }

    /**
     * 删除第一个节点
     */
    public void removeFirst() {
        if (head == null) {
            throw new RuntimeException("链表为空，无法删除");
        }

        // 将head的next赋值给head
        head = head.next;
    }

    /**
     * 根据索引删除指定节点
     * @param index 索引
     */
    public void remove(int index) {

        if (index == 0) {
            // 如果索引为零，相当于删除第一个节点
            removeFirst();
            return;
        }

        // 查找待删除节点的上一个节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw new RuntimeException("索引异常");
        }

        // 查找待删除节点
        Node removed = prev.next;
        if (removed == null) {
            throw new RuntimeException("索引异常");
        }

        // 使被删除接的上一个节点next指向被删除节点的next
        prev.next = removed.next;
    }

    /**
     * 递归遍历
     */
    public void loop3() {
        recursion(head);
    }

    // 递归
    private void recursion(Node curr) {
        if (curr == null) {
            return;
        }

        System.out.println("before-" + curr.value);
        recursion(curr.next);
        System.out.println("after-" + curr.value);
    }
}


